#include <iostream>

using namespace std;

/*
Find largest all 1s sub-matrix in a binary matrix. The resultant sub-matrix 
is not necessarily a square sub-matrix. Time complexity O(m*n), space complexity O(min(m,n)).

Example:

    1 1 0 0 1 0
    0 1 1 1 1 1
    1 1 1 1 1 0
    0 0 1 1 0 0

Largest all 1s sub-matrix is from (1,1) to (2,4).

    1 1 1 1
    1 1 1 1

If the existing matrix is N*N and the sub-matrix is also m*m (square), we can use
DP with time complexity O(N*N), which is in DP solutions MaxSqare.cpp.

*/

#define ROW 10  
#define COL 10  
      
extern int LargestArea(int arr[], int len);

int FindMaxSubmatrix(int A[ROW][COL])  
{  
    int i, j;  
    int max, cur_max;  
    cur_max = 0;  
      
    //Calculate Auxilary matrix  
    for (i=1; i<ROW; i++)  
        for(j=0; j<COL; j++)  
        {  
            if(A[i][j] == 1)  
                A[i][j] = A[i-1][j] + 1;  
        }  
      
    //Calculate maximum area in S for each row  
    for (i=0; i<ROW; i++)  
    {       
        max = LargestArea(A[i], COL);  
        if (max > cur_max)  
            cur_max = max;  
    }  
      
    //Regenerate Orignal matrix  
    for (i=ROW-1; i>0; i--)  
        for(j=0; j<COL; j++)  
        {  
            if(A[i][j])  
                A[i][j] = A[i][j] - A[i-1][j];  
        }  
      
    return cur_max;  
}  